package week5;

/**
 * 排序展示了排序和搜索在一个对象数组
 *
 * @author Lewis and Chase
 * @version 4.0 
 */
public class Sorting 
{
    /**
     * 用选择对指定的整数数组进行排序
     * 排序算法
     *
     * @param data 要排序的数组
     */
     public static <T extends Comparable<T>>
		void selectionSort(T[] data)
    {
        int min;
        T temp;
        
        for (int index = 0; index < data.length-1; index++)
        {
            min = index;
            for (int scan = index+1; scan < data.length; scan++)
                if (data[scan].compareTo(data[min])<0)
                    min = scan;
			
            swap(data, min, index);
        }
    }
	
	/**
	 * 对数组中的元素进行交换。用于各种排序算法。.
	 * 
	 * @param data  元素被交换的数组
	 * @param index1 要交换的第一个元素的索引
	 * @param index2 要交换的第二个元素的索引
	 */
	private static <T extends Comparable<T>> 
		void swap(T[] data, int index1, int index2)
	{
		T temp = data[index1];
		data[index1] = data[index2];
		data[index2] = temp;
	}
	
    /**
     * 使用插入对指定的对象数组进行排序
     * 排序算法.
     *
     * @param data 被搜索的数组
     */
    public static <T extends Comparable<T>> 
		void insertionSort(T[] data)
    {
        for (int index = 1; index < data.length; index++)
        {
            T key = data[index];
            int position = index;
			
            // 将更大的值转移到右边
            while (position > 0 && data[position-1].compareTo(key) > 0)
            {
                data[position] = data[position-1];
                position--;
            }
			
            data[position] = key;
        }
    }
	
    /**
     * 使用冒泡排序对指定的数组进行排序
     * 算法
     *
     * @param data 被排序的数组
     */
    public static <T extends Comparable<T>> 
		void bubbleSort(T[] data)
    {
        int position, scan;
        T temp;
		
        for (position =  data.length - 1; position >= 0; position--)
        {
            for (scan = 0; scan <= position - 1; scan++)
            {
                if (data[scan].compareTo(data[scan+1]) > 0)
                    swap(data, scan, scan + 1);
            }
        }
    }

    /**
     * 使用归并排序对指定的数组进行排序
     * 算法
     *
     * @param data 被排序的数组
     */
	public static <T extends Comparable<T>>
		void mergeSort(T[] data)
	{
		mergeSort(data, 0, data.length - 1);
	}
	
    /**
	 * 递归地对指定数组中的对象进行排序
	 * 归并排序算法
     *
     * @param data 被排序的算法
     * @param min  第一个元素的索引
     * @param max  最后一个元素的索引
     */
	private static <T extends Comparable<T>>
		void mergeSort(T[] data, int min, int max)
	{
		if (min < max)
		{
			int mid = (min + max) / 2;
			mergeSort(data, min, mid);
			mergeSort(data, mid+1, max);
			merge(data, min, mid, max);
		}
	}
	
	/**
     * 合并指定数组的两个排序子数组。
     *
     * @param data 被排序的数组
     * @param first 第一个子数组的开始索引
     * @param mid 第一个子数组的结束索引
     * @param last 第二个子数组的结束索引
     */
	@SuppressWarnings("unchecked")
	private static <T extends Comparable<T>>
		void merge(T[] data, int first, int mid, int last)
	{
		T[] temp = (T[])(new Comparable[data.length]);
		
		int first1 = first, last1 = mid;  // 第一个子数组的端点
		int first2 = mid+1, last2 = last;  // 第二个子数组的端点
		int index = first1;  // 下一个在临时数组中打开的索引
		
		//将紫薯组中的元素复制到temp中知道子数组中的元素被用尽
		while (first1 <= last1 && first2 <= last2)
		{
			if (data[first1].compareTo(data[first2]) < 0)
			{
				temp[index] = data[first1];
				first1++;
			}
			else
			{
				temp[index] = data[first2];
				first2++;
			}
			index++;
		}
		
		//  如果第一个子数组有元素，则保留第一个数组中保留剩余的元素
		while (first1 <= last1)
		{
			temp[index] = data[first1];
			first1++;
			index++;
		}
		
		//  如果第二个子数组有元素，则保留第二个数组中保留剩余的元素
		while (first2 <= last2)
		{
			temp[index] = data[first2];
			first2++;
			index++;
		}
		
		//  将合并后的数据复制到原始数组中
		for (index = first; index <= last; index++)
			data[index] = temp[index];
   }

	/**
	 * 使用快速排序算法对指定的对象数组进行排序。
	 * 
	 * @param data 被排序的数组
	 */
	public static <T extends Comparable<T>> 
		void quickSort(T[] data)
	{
		quickSort(data, 0, data.length - 1);
	}
	
	/**
	 * 用快速排序算法递归的对指定数组进行排序
	 * @param data 被排序的数组
	 * @param min  在范围内被排序的最小值索引
	 * @param max  在范围内被排序的最大值索引
	 */
	private static <T extends Comparable<T>> 
		void quickSort(T[] data, int min, int max)
	{
		if (min < max)
		{
			// 创建分区
			int indexofpartition = partition(data, min, max);
			
			// 排序左分区（低一级分区）
			quickSort(data, min, indexofpartition - 1);
			
			// 排序右分区（高一级分区）
			quickSort(data, indexofpartition + 1, max);
		}
	}
	
	/**
	 * 使用快速排序算法找到分区
	 * 
	 * @param data 被排序的数组
	 * @param min  范围内被排序的最小值索引
	 * @param max  范围内被排序的最大值索引
	 */
	private static <T extends Comparable<T>> 
		int partition(T[] data, int min, int max)
	{
		T partitionelement;
		int left, right;
		int middle = (min + max) / 2;
		
		// 使用中间的数据作为分区元素
		partitionelement = data[middle];
		// 现在移动它出这个方式
		swap(data, middle, min);
		
		left = min;
		right = max;
		
		while (left < right)
		{
			// 搜索大于分区元素的元素
			while (left < right && data[left].compareTo(partitionelement) <= 0)
				left++;
			
			// 搜索小于分区元素的元素
			while (data[right].compareTo(partitionelement) > 0)
				right--;
			
			// 交换元素
			if (left < right)
				swap(data, left, right);
		}
		
		// 将分区元素移动到适合的位置
		swap(data, min, right);
		
		return right;
	}
}

